package cn.hycat.leetcode.middle;

import java.util.concurrent.Callable;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
//378. 有序矩阵中第 K 小的元素
//        给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
//        请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
//
//        你必须找到一个内存复杂度优于 O(n2) 的解决方案。示例 1：
//
//        输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
//        输出：13
//        解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
//        示例 2：
//
//        输入：matrix = [[-5]], k = 1
//        输出：-5
public class L378有序数组第K小的元素 {
    static class Node {
        int nums;    //小于等于m的数量
        int ans; //最靠近m的数字

        public Node(int nums, int ans) {
            this.nums = nums;
            this.ans = ans;
        }
    }
    public static int kthSmallest(int[][] matrix, int k) {
        int ans = 0;
        int N = matrix.length - 1;
        int M = matrix[0].length - 1;
        int l = matrix[0][0], r = matrix[N][M];
        while(l <= r) {
            int m = l + ((r - l) >> 1);
            if(getNums(matrix, m).nums < k) {
                l = m + 1;
            } else {
                ans = getNums(matrix, m).ans;
                r = m - 1;
            }
        }
        return ans;
    }

    public static Node getNums(int[][]matrix, int m) { //返回结果：m的信息
        int nums = 0;
        int ans = Integer.MIN_VALUE;
        int N = 0;
        int M = matrix[0].length - 1;
        while(N < matrix.length && M >= 0) {
            if(m < matrix[N][M]) {
                M--;
            } else if(m >= matrix[N][M]) {
                nums += M+1;
                ans = Math.max(matrix[N][M], ans);
                N++;
            }
        }
        return new Node(nums, ans);
    }

    private static Object obj = new Object();
    private static ReentrantLock lock = new ReentrantLock();
    public static void main(String[] args) {

        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("尝试获得锁");
                try {
                    synchronized (obj) {
                        System.out.println("获得锁成功");
                    }
                }finally {
                    System.out.println("打断成功");
                }
            }
        }, "t1");

//        while(true) {
//            synchronized (obj) {
//                System.out.println("干扰线程来啦");
//            }
//        }

        t1.start();
        t1.interrupt();
    }
}
